package com.zto.sch.leetcode.链表反转;

import java.util.Stack;

public class RevNodeTest {
    public static void main(String[] args) {
        //构建单链表
        Node node8 = new Node(8, null);
        Node node7 = new Node(7, node8);
        Node node6 = new Node(6, node7);
        Node node5 = new Node(5, node6);
        Node node4 = new Node(4, node5);
        Node node3 = new Node(3, node4);
        Node node2 = new Node(2, node3);
        Node head = new Node(1, node2);
        Node newHead = revNode(head, 4);
        printnewHead(newHead);
    }

    //打印链表
    private static void printnewHead(Node newHead) {
        Node tmpNode = newHead;
        while (true) {
            if (tmpNode != null) {
                System.out.print(tmpNode.value+ " ");
                if (tmpNode.next != null) {
                    tmpNode = tmpNode.next;
                } else {
                    break;
                }
            }
        }

    }

    public static Node revNode(Node head,int len){
        if (head.next == null || len <= 1) {//如果只有一个结点，则直接返回
            return head;
        }
        Node newHead = null;//返回的新的链表的头部
        Node curNode = head;//临时节点，入栈使用
        Node tmpNode = null;//临时节点： 出栈使用
        Node preNode = null;//N 个节点的最后一个，用于N+1个节点往前连接
        Node noRevNode = null;//记录每次入栈的第一个，有可能是不逊转的。
        Node preNodeSer = null;//弹出stack时的前置节点
        //入栈
        Stack<Node> stack = new Stack();
        int flag = 1;//为1：可以旋转，0为不可以旋转，不足len
        while(flag == 1){
            //入栈
            for (int i = 1; i <= len; i++) {
                if(i == 1){
                    noRevNode = curNode;
                }
                stack.push(curNode);
                if (curNode.next != null) {
                    curNode = curNode.next;
                } else {
                    //把n的最后一个结点接在现在的节点上。
                    flag = 0; //可以旋转，
                    break;//不足len，不旋转
                }
            }

            //出栈
            if (stack.size() == len) { //旋转
                for (int i = 1; i <= len; i++) {
                    Node popNode = stack.pop();
                    tmpNode = popNode;

                    if (newHead == null) {//第一次弹出，就是新的首节点，要不然首节点已经被占说明是>1次的弹出
                        newHead = popNode;
                        preNodeSer = popNode;
                    } else {
                        preNodeSer.next = tmpNode;
                        preNodeSer = tmpNode;
                        if(i == len){//记录下次节点需要连上的上次的节点
                            preNode = popNode;// preNode = tmpNode;
                            if (0 == flag) {
                                preNode.next = null;//要不然会循环打印
                            }
                        }
                    }
                }
            } else {//不旋转
                if (newHead == null) {//如果len>size时使用
                    return head;
                }
                preNode.next = noRevNode;
            }

            if (tmpNode.next == null) {
                flag = 0;
            }
        }
        return newHead;
    }
}